package 剑指offer;

import common.ListNode;

/**
 * @author zhangmin
 * @create 2021-11-21 14:45
 *
 * 双指针
 */
public class day11_18_22 {

    /**===========================================================================================================================
     * 剑指 Offer 18. 删除链表的节点
     * 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
     * 双指针，一个指向前一个结点，一个指向当前节点
     * */
    public ListNode deleteNode1(ListNode head, int val) {
        if (head.val==val) return head.next;
        ListNode root=head;
        ListNode pre=head,cur=head;
        while (cur.next!=null){
            pre=cur;
            cur=cur.next;
            if (cur.val==val){
                pre.next=cur.next;
                return root;
            }
        }
        if (cur.val==val) pre.next=null;
        return root;
    }
    //题解：先定位，再删除
    public ListNode deleteNode(ListNode head, int val) {
        if (head.val==val) return head.next;
        ListNode pre=head,cur=head.next;
        while (cur!=null&&cur.val!=val){
            pre=cur;
            cur=cur.next;
        }
        if (cur!=null) pre.next=cur.next;
        return head;
    }

    /**===========================================================================================================================
     * 剑指 Offer 22. 链表中倒数第k个节点
     * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
     * 快慢指针，快指针指向k+1节点，当快指针到最后的时候，慢指针的位置就是倒数第k和节点
     * */
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast=head,slow=head;
        while (fast.next!=null&&k>1){
            fast=fast.next;
            k--;
        }
        while (fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}
